#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <limits.h>
#include "../include/cache.h"
#include "../include/eviction.h"

// 获取当前时间
time_t get_current_time(void)
{
    return time(NULL);
}

/**
    哈希函数
    将字符串转化为哈希值
    使用DJB2算法 核心思想是 将字符串中的每个字符与一个质数相乘，然后累加得到最终的哈希值
    质数的选择是 5381 因为它是质数，而且是一个比较小的质数，可以减少哈希冲突 （5381是经验值）
    5381 是一个比较小的质数，可以减少哈希冲突
*/
unsigned int hash_function(const char* key, int bucket_count)
{
    unsigned int hash = 5381;
    // 让字符串的值加上之前累加的hash值*33
    for(int i = 0; key[i] != '\0'; i++)
    {
        // 33 是一个经验值，可以减少哈希冲突
        hash = hash*33 +key[i];
    }
    // 返回到桶的索引
    return hash%bucket_count;
}

/**
 * 设置缓存,有就更新，没有就创建
 * @param cache 缓存指针
 * @param key 键
 * @param value 值
 * @param ttl 过期时间
 * @return 成功返回0 失败返回 -1
 */
int cache_set(Cache* cache, const char* key, const char* value, int ttl) {
    printf("DEBUG: cache_set called with key='%s', value='%s', ttl=%d\n", key, value, ttl);
    // 1. 定位桶
    int bucket_index = hash_function(key, cache->bucket_count);
    CacheBucket* bucket = &cache->buckets[bucket_index];
    printf("DEBUG: bucket_index=%d\n", bucket_index);
    // 2. 加锁
    pthread_mutex_lock(&bucket->lock);
    CacheNode* current = bucket->head;
    while(current)
    {
        // 3. 遍历链表查找key
        if(strcmp(current->key, key) == 0)
        {
            // 4. 如果找到，更新value和时间
            // strdup 复制字符串，返回一个指向新分配内存的指针
            // 释放原来的value
            free(current->value);
            current->value = strdup(value);
            if(ttl > 0)
            {
                current->expire_time = get_current_time() + ttl;
            }else{
                current->expire_time = 0;
            }
            current->last_access = get_current_time();
            // 更新统计信息
            pthread_rwlock_wrlock(&cache->stats_lock);
            cache->stats.hits++;
            current->access_count++;
            pthread_rwlock_unlock(&cache->stats_lock);
            // 解锁
            pthread_mutex_unlock(&bucket->lock);
            return 0;
        }
        current = current->next;
    }
        // 出来说明没有找到
        // 5. 如果没有找到，先判断容量和内存限制
        size_t new_key_len = strlen(key);
        size_t new_value_len = strlen(value);
        pthread_rwlock_rdlock(&cache->stats_lock);
        // 检查是否超节点数或者超内存数
        int would_exceed_nodes = (cache->total_nodes + 1 > cache->max_nodes);
        int would_exceed_memory = (cache->current_memory + new_key_len + new_value_len > cache->max_memory);
        pthread_rwlock_unlock(&cache->stats_lock);
        if (would_exceed_nodes || would_exceed_memory) {
            // 尝试淘汰一个节点
            if (eviction_evict(cache) == 0) {
                // 淘汰成功，重新判断限制
                pthread_rwlock_rdlock(&cache->stats_lock);
                would_exceed_nodes = (cache->total_nodes + 1 > cache->max_nodes);
                would_exceed_memory = (cache->current_memory + new_key_len + new_value_len > cache->max_memory);
                pthread_rwlock_unlock(&cache->stats_lock);
                if (would_exceed_nodes || would_exceed_memory) {
                    pthread_mutex_unlock(&bucket->lock);
                    return -1;
                }
            } else {
                // 淘汰失败，直接返回
                pthread_mutex_unlock(&bucket->lock);
                return -1;
            }
        }
        // 走到这说明节点数 和 内存大小 都没有超限
        // 6. 创建新节点插入链表头
        CacheNode* new_node = create_cache_node(key, value, ttl);
        if(!new_node)
        {
            printf("DEBUG: Failed to create cache node\n");
            pthread_mutex_unlock(&bucket->lock);
            return -1;
        }
        printf("DEBUG: Created new node successfully\n");
        // 头插法
        new_node->next = bucket->head;
        bucket->head = new_node;
        // 6. 更新节点数和内存统计（线程安全）
        pthread_rwlock_wrlock(&cache->stats_lock);
        cache->total_nodes++;
        cache->current_memory += strlen(key) + strlen(value);
        pthread_rwlock_unlock(&cache->stats_lock);
        // 7. 解锁
        pthread_mutex_unlock(&bucket->lock);
        return 0;
}

/**
 * 获取缓存，有就返回，没有就返回NULL
 * @param cache 缓存指针
 * @param key 键
 * @return 缓存节点指针
 */
CacheNode* cache_get(Cache* cache, const char* key)
{
    printf("DEBUG: cache_get called with key='%s'\n", key);
    // 1. 定位桶
    int bucket_index = hash_function(key, cache->bucket_count);
    CacheBucket *bucket = &(cache->buckets[bucket_index]);
    printf("DEBUG: bucket_index=%d\n", bucket_index);
    // 2. 加锁
    pthread_mutex_lock(&bucket->lock);
    CacheNode* current = bucket->head;
    // 3. 遍历链表查找key
    while(current)
    {
        if(strcmp(current->key, key) == 0)
        {
            // 4. 如果找到,查看是否过期
            if(current->expire_time > 0 && current->expire_time <= get_current_time())
            {
                // 5. 如果过期，删除节点并更新miss统计
                // 调用删除节点之前要解锁，否则会死锁
                pthread_mutex_unlock(&bucket->lock);
                // 还要去遍历，直接就地free可以提升性能
                cache_delete(cache, key);
                // destroy_cache_node(current);
                // 加锁
                pthread_mutex_lock(&bucket->lock);
                pthread_rwlock_wrlock(&cache->stats_lock);
                cache->stats.misses++;
                pthread_rwlock_unlock(&cache->stats_lock);
                pthread_mutex_unlock(&bucket->lock);
                printf("DEBUG: Key expired, deleted and returned NULL\n");
                return NULL;
            }
            // 6. 如果没过期，更新访问时间和hit统计，返回节点
            current->last_access = get_current_time();
            current->access_count++;
            pthread_rwlock_wrlock(&cache->stats_lock);
            cache->stats.hits++;
            pthread_rwlock_unlock(&cache->stats_lock);
            pthread_mutex_unlock(&bucket->lock);
            printf("DEBUG: Found key, returning node\n");
            return current;
        }
        current = current->next;
    }
    // 7. 没有找到，更新统计并返回NULL
    pthread_rwlock_wrlock(&cache->stats_lock);
    cache->stats.misses++;
    pthread_rwlock_unlock(&cache->stats_lock);
    pthread_mutex_unlock(&bucket->lock);
    printf("DEBUG: Key not found\n");
    return NULL;
}

/**
 * 删除缓存
 * @param cache 缓存指针
 * @param key 键
 * @return 0成功，-1失败
 */
int cache_delete(Cache* cache, const char* key)
{
    // 1. 定位桶
    int bucket_index = hash_function(key, cache->bucket_count);
    CacheBucket* bucket = &cache->buckets[bucket_index];
    // 2. 加锁
    pthread_mutex_lock(&bucket->lock);
    CacheNode* current = bucket->head;
    CacheNode* prev = NULL;
    while(current)
    {
        if(strcmp(current->key, key) == 0)
        {
            // 3. 如果找到，删除节点    
            // prev不为空说明不是头节点，需要将prev的next指向current的next
            if(prev)
            {
                prev->next = current->next;
            }
            else
            {
                // 是头结点
                bucket->head = current->next;
            }
            // 删除元素，将节点的内存释放
            // 先计算key和value的长度，释放之后不能使用current->key和current->value，空指针
            int key_len = strlen(current->key);
            int value_len = strlen(current->value);
            destroy_cache_node(current);
            // 想要多线程安全，一定要记得加锁
            // 更新节点数和内存统计（多线程情况下，需要加锁）
            pthread_rwlock_wrlock(&cache->stats_lock);
            cache->total_nodes--;
            cache->current_memory -= key_len + value_len;
            // 这里应该是evictions，因为是被主动删除的
            cache->stats.evictions++;
            pthread_rwlock_unlock(&cache->stats_lock);
            // 解锁
            pthread_mutex_unlock(&bucket->lock);
            return 0;
        }
        // 递归遍历链表 条件
        prev = current;
        current = current->next;
    }
    // 没有找到，返回-1
    pthread_mutex_unlock(&bucket->lock);
    return -1;
}

/**
 * 检查键是否存在
 * @param cache 缓存指针
 * @param key 键
 * @return 1存在，0不存在
 */
int cache_exists(Cache* cache, const char* key)
{
    CacheNode* node = cache_get(cache, key);
    //在get中有处理miss和hit的统计，所以这里直接返回
    return node != NULL ? 1 : 0;
}

/**
 * 获取键的剩余生存时间
 * @param cache 缓存指针
 * @param key 键
 * @return 剩余秒数，-2表示不存在，-1表示永不过期，其他表示剩余秒数
 */
int cache_ttl(Cache* cache, const char* key)
{
    // 调用cache_get()函数，如果存在返回剩余时间，不存在返回-1
    // 在get中有处理miss和hit的统计，所以这里直接返回
    CacheNode* node = cache_get(cache, key);
    if(!node)
        return -2;
    if(node->expire_time == 0)
        return -1;  // 永不过期
    time_t current_time = get_current_time();
    // 只读操作，不需要加锁
    int ttl = node->expire_time - current_time;
    // 如果ttl大于0，返回ttl，否则返回-2
    return ttl > 0 ? ttl : -2;
}

/**
 * 设置键的过期时间
 * @param cache 缓存指针
 * @param key 键
 * @param ttl 过期时间（秒）
 * @return 0成功，-1失败
 */
int cache_expire(Cache* cache, const char* key, int ttl)
{
    // 调用cache_get函数，设置过期时间
    // 在get中有处理miss和hit的统计，所以这里直接返回
    CacheNode* node = cache_get(cache, key);
    int bucket_index = hash_function(key, cache->bucket_count);
    // 如果存在，设置过期时间，返回0
    if(node)
    {
        // 多线程安全，需要加锁
        pthread_mutex_lock(&(cache->buckets[bucket_index].lock));
        // ttl = 0 表示永不过期，设置为 0
        // ttl > 0 表示有过期时间，设置为当前时间 + ttl
        node->expire_time = (ttl > 0) ? (get_current_time() + ttl) : 0;
        pthread_mutex_unlock(&(cache->buckets[bucket_index].lock));
        return 0;
    }
    // 不存在，返回-1
    return -1;
}

/**
 * 清理过期缓存
 * @param cache 缓存指针
 * @return 清理的节点数
 */
int cache_clean_expired(Cache* cache)
{
    int count = 0;
    time_t current_time = get_current_time();
    
    // 遍历所有桶
    for(int i = 0; i < cache->bucket_count; i++)
    {
        CacheBucket* bucket = &cache->buckets[i];
        // 访问每个桶都要加锁
        pthread_mutex_lock(&bucket->lock);
        CacheNode* current = bucket->head;
        CacheNode* prev = NULL;
        while(current)
        {
            // 检查是否过期
            if(current->expire_time > 0 && current->expire_time < current_time)
            {
                // 删除过期节点
                CacheNode* next = current->next;
                
                if(prev == NULL)
                {
                    // 说明删除头节点
                    bucket->head = next;
                }
                else
                {
                    // 删除中间节点
                    prev->next = next;
                }
                
                // 保存长度用于统计
                int key_len = strlen(current->key);
                int value_len = strlen(current->value);
                
                // 释放节点
                destroy_cache_node(current);
                
                // 线程安全地更新统计信息
                pthread_rwlock_wrlock(&cache->stats_lock);
                cache->total_nodes--;
                cache->current_memory -= key_len + value_len;
                // 这里应该是expires，因为是过期被清理的
                cache->stats.expires++;
                pthread_rwlock_unlock(&cache->stats_lock);   
                count++;
                current = next;
            }
            else
            {
                prev = current;
                current = current->next;
            }
        }
        // 解锁
        pthread_mutex_unlock(&bucket->lock);
    }
    // 返回清理的节点数
    return count;
}

/**
 * 初始化缓存
 * @param bucket_count 桶数量
 * @param max_nodes 最大节点数
 * @param max_memory 最大内存
 * @param eviction_policy 淘汰策略
 * @return 缓存指针
 */
Cache* cache_init(int bucket_count, int max_nodes, size_t max_memory, int eviction_policy)
{
    Cache* cache = (Cache*) malloc(sizeof(Cache));
    if(!cache)
        return NULL;
    // 初始化桶，申请内存
    cache->bucket_count = bucket_count;
    cache->buckets = (CacheBucket*) malloc(bucket_count * sizeof(CacheBucket));
    if(!cache->buckets)
    {
        free(cache);
        return NULL;
    }
    // 初始化桶，初始化锁
    for(int i = 0; i < bucket_count; i++)
    {
        cache->buckets[i].head = NULL;
        pthread_mutex_init(&cache->buckets[i].lock, NULL);
    }
    // 初始化统计信息
    cache->stats.hits = 0;
    cache->stats.misses = 0;
    cache->stats.evictions = 0;
    cache->stats.expires = 0;
    // 初始化节点数和内存统计
    cache->total_nodes = 0;
    cache->current_memory = 0;
    // 初始化最大节点数和最大内存
    cache->max_nodes = max_nodes;
    cache->max_memory = max_memory;
    // 初始化淘汰策略
    cache->eviction_policy = eviction_policy;
    // 初始化统计信息读写锁
    pthread_rwlock_init(&cache->stats_lock, NULL);
    
    // 初始化主动过期清理相关
    // 默认不启动清理线程
    cache->cleanup_running = 0;
    // 默认10秒清理一次
    cache->cleanup_interval = 10;
    // 每次最多清理20个过期key
    cache->max_expired_per_cleanup = 20;
    // 初始化清理线程锁
    pthread_mutex_init(&cache->cleanup_lock, NULL);
    
    // 初始化随机数种子（用于清理线程的随机采样）
    srand(time(NULL));
    
    return cache;
}

/**
 * 销毁缓存
 * @param cache 缓存指针
 */
void cache_destroy(Cache* cache)
{
    if(!cache)
        return;
    // 销毁每个桶
    for(int i = 0; i < cache->bucket_count; i++)
    {
        CacheBucket* bucket = &cache->buckets[i];
        // 销毁每个桶的锁
        pthread_mutex_destroy(&bucket->lock);
        // 销毁每个桶的链表
        CacheNode* current = bucket->head;
        while(current)
        {
            CacheNode* next = current->next;
            destroy_cache_node(current);
            current = next;
        }
    }
    // 销毁统计信息读写锁
    pthread_rwlock_destroy(&cache->stats_lock);
    
    // 停止并销毁清理线程
    cache_stop_cleanup_thread(cache);
    // 销毁清理线程锁
    pthread_mutex_destroy(&cache->cleanup_lock);
    
    // 销毁桶
    free(cache->buckets);
    // 销毁缓存
    free(cache);
}

/**
 * 创建缓存节点
 * @param key 键
 * @param value 值
 * @param ttl 过期时间
 * @return 新节点指针
 */
CacheNode* create_cache_node(const char* key, const char* value, int ttl)
{
    CacheNode* node = (CacheNode*) malloc(sizeof(CacheNode));
    if(!node)
        return NULL;
    node->key = strdup(key);
    if(!node->key) {
        free(node);
        return NULL;
    }
    node->value = strdup(value);
    if(!node->value) {
        free(node->key);
        free(node);
        return NULL;
    }
    // ttl = 0 表示永不过期，设置为 0
    // ttl > 0 表示有过期时间，设置为当前时间 + ttl
    node->expire_time = (ttl > 0) ? (get_current_time() + ttl) : 0;
    node->last_access = get_current_time();
    //访问次数为 0
    node->access_count = 0;
    node->next = NULL;
    return node;
}

/**
 * 销毁缓存节点
 * @param node 节点指针
 */
void destroy_cache_node(CacheNode* node)
{
    if(!node)
        return;
    free(node->key);
    free(node->value);
    free(node);
}

/** 
 * 获取缓存统计信息
 * @param cache 缓存指针
 * @param hits 命中次数
 * @param misses 未命中次数
 * @param evictions 淘汰次数
 * @param expires 过期次数
 * @note 这里的参数都是传出参数，所以需要使用指针
 */
void cache_get_stats(Cache* cache, long long* hits, long long* misses, 
                    long long* evictions, long long* expires)
{
    pthread_rwlock_rdlock(&cache->stats_lock);
    // 如果参数为空，则不更新
    if(hits) *hits = cache->stats.hits;
    if(misses) *misses = cache->stats.misses;
    if(evictions) *evictions = cache->stats.evictions;
    if(expires) *expires = cache->stats.expires;
    pthread_rwlock_unlock(&cache->stats_lock);
}

/**
 * 打印缓存统计信息
 * @param cache 缓存指针
 * @param name 名称
 */
void cache_print_stats(Cache* cache, const char* name)
{
    long long hits, misses, evictions, expires;
    cache_get_stats(cache, &hits, &misses, &evictions, &expires);
    printf("==== 缓存统计信息 [%s] ====""\n", name ? name : "");
    printf("命中次数: %lld\n", hits);
    printf("未命中次数: %lld\n", misses);
    printf("淘汰次数: %lld\n", evictions);
    printf("过期次数: %lld\n", expires);
    printf("当前节点数: %d\n", cache->total_nodes);
    printf("当前内存: %zu bytes\n", cache->current_memory);
    printf("最大节点数: %d\n", cache->max_nodes);
    printf("最大内存: %zu bytes\n", cache->max_memory);
    printf("============================\n");
}

/**
 * 自适应过期清理（类似Redis的主动过期）
 * @param cache 缓存指针
 * @return 清理的过期节点数
 */
int cache_cleanup_expired_adaptive(Cache* cache) {
    int cleaned = 0;
    time_t current_time = get_current_time();
    
    // 计算需要检查的桶数量（采样策略）
    int buckets_to_check = cache->bucket_count;
    // 如果桶的个数很多，只检查一部分（类似Redis的采样）默认检查16个桶
    if (cache->bucket_count > 16) {
        buckets_to_check = 16;
    }
    
    // 随机选择起始桶（避免每次都从同一个桶开始）
    int start_bucket = rand() % cache->bucket_count;
    // 遍历需要检查的桶，如果清理的过期节点数小于最大清理数，则继续检查
    for (int i = 0; i < buckets_to_check && cleaned < cache->max_expired_per_cleanup; i++) {
        int bucket_index = (start_bucket + i) % cache->bucket_count;
        CacheBucket* bucket = &cache->buckets[bucket_index];
        
        pthread_mutex_lock(&bucket->lock);
        CacheNode* current = bucket->head;
        CacheNode* prev = NULL;
        // current不为空，并且清理的过期节点数小于最大清理数，则继续检查
        while (current && cleaned < cache->max_expired_per_cleanup) {
            // 检查是否过期
            if (current->expire_time > 0 && current->expire_time <= current_time) {
                // 删除过期节点
                CacheNode* next = current->next;
                
                if (prev == NULL) {
                    bucket->head = next;
                } else {
                    prev->next = next;
                }
                
                // 保存长度用于统计
                int key_len = strlen(current->key);
                int value_len = strlen(current->value);
                
                // 释放节点
                destroy_cache_node(current);
                
                // 线程安全地更新统计信息
                pthread_rwlock_wrlock(&cache->stats_lock);
                cache->total_nodes--;
                cache->current_memory -= key_len + value_len;
                cache->stats.expires++;
                pthread_rwlock_unlock(&cache->stats_lock);
                
                cleaned++;
                current = next;
            } else {
                prev = current;
                current = current->next;
            }
        }
        
        pthread_mutex_unlock(&bucket->lock);
    }
    
    return cleaned;
}

/**
 * 清理线程函数
 * @param arg 缓存指针
 * @return NULL
 * @note 清理线程函数，每隔一段时间执行一次清理操作，如果清理的过期节点数大于0，则缩短清理间隔，如果清理的过期节点数为0，则延长清理间隔
 */
void* cache_cleanup_thread(void* arg) {
    Cache* cache = (Cache*)arg;
    
    while (cache->cleanup_running) {
        // 执行自适应清理
        int cleaned = cache_cleanup_expired_adaptive(cache);
        
        if (cleaned > 0) {
            printf("清理线程: 清理了 %d 个过期节点\n", cleaned);
        }
        
        // 根据清理结果调整清理间隔
        if (cleaned == cache->max_expired_per_cleanup) {
            // 清理了最大数量的过期key，说明过期key很多，缩短清理间隔
            cache->cleanup_interval = (cache->cleanup_interval > 1) ? 
                                    cache->cleanup_interval - 1 : 1;
        } else if (cleaned > 0 && cleaned < cache->max_expired_per_cleanup) {
            // 清理了一些过期key，但没达到最大数量，保持当前间隔
            // 可以稍微缩短间隔，因为还有过期key
            if (cache->cleanup_interval > 5) {
                cache->cleanup_interval--;
            }
        } else if (cleaned == 0) {
            // 没有过期key，延长清理间隔
            cache->cleanup_interval = (cache->cleanup_interval < 60) ? 
                                    cache->cleanup_interval + 1 : 60;
        }
        
        // 等待下一次清理
        // 计时器，如果清理线程运行状态为1，则等待下一次清理
        for (int i = 0; i < cache->cleanup_interval && cache->cleanup_running; i++) {
            sleep(1);
        }
    }
    
    return NULL;
}

/**
 * 启动清理线程
 * @param cache 缓存指针
 * @return 0成功，-1失败
 */
int cache_start_cleanup_thread(Cache* cache) {
    // 如果缓存指针为空，或者清理线程已经运行，则返回-1
    if (!cache || cache->cleanup_running) {
        return -1;
    }
    // 设置清理线程运行状态为1
    cache->cleanup_running = 1;
    // 创建清理线程
    if (pthread_create(&cache->cleanup_thread, NULL, cache_cleanup_thread, cache) != 0) {
        cache->cleanup_running = 0;
        return -1;
    }
    
    printf("启动过期清理线程\n");
    return 0;
}

/**
 * 停止清理线程
 * @param cache 缓存指针
 * @note 设置清理线程运行状态为0，等待清理线程结束
 */
void cache_stop_cleanup_thread(Cache* cache) {
    // 如果缓存指针为空，或者清理线程没有运行，则返回
    if (!cache || !cache->cleanup_running) {
        return;
    }
    // 设置清理线程运行状态为0
    cache->cleanup_running = 0;
    // 等待清理线程结束
    pthread_join(cache->cleanup_thread, NULL);
    printf("停止过期清理线程\n");
}
